package com.cet.algorithm.二叉树.对称二叉树;

import java.util.Deque;
import java.util.LinkedList;

/**
 * @program: algorithm
 * @description: 相同的树
 * @author: 陈恩涛
 * @create: 2022-07-19 15:17
 **/
public class LC100 {

    public static void main(String[] args) {
        final TreeNode p = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        final TreeNode q = new TreeNode(1, new TreeNode(2), new TreeNode(3));
        System.out.println(isSameTree(p, q));

        final TreeNode r = new TreeNode(1, new TreeNode(2), null);
        final TreeNode s = new TreeNode(1, null, new TreeNode(2));
        System.out.println(isSameTree(r, s));

    }

    /**
     * tlr
     * @param p
     * @param q
     * @return
     */
    public static boolean isSameTree(TreeNode p, TreeNode q) {
        final Deque<TreeNode> deque = new LinkedList<>();
        deque.offerFirst(p);
        deque.offerLast(q);
        while (!deque.isEmpty()) {
            final TreeNode first = deque.pollFirst();
            final TreeNode second = deque.pollLast();
            if (first == null && second == null) {
                continue;
            }

            if (first == null || second == null || first.val != second.val) {
                return false;
            }
            deque.offerLast(second.left);
            deque.offerLast(second.right);
            deque.offerFirst(first.left);
            deque.offerFirst(first.right);
        }
        return true;
    }

    /**
     * 递归法
     * @param tree1
     * @param tree2
     * @return
     */
    private boolean compare(TreeNode tree1, TreeNode tree2) {

        if (tree1 == null && tree2 != null) {
            return false;
        }
        if (tree1 != null && tree2 == null) {
            return false;
        }
        if (tree1 == null && tree2 == null) {
            return true;
        }
        if (tree1.val != tree2.val) {
            return false;
        }
        // 比较外侧
        final boolean compareLeft = compare(tree1.left, tree2.left);
        // 比较内侧
        final boolean compareRight = compare(tree1.right, tree2.right);
        return compareLeft && compareRight;
    }
}
